package Sort;

import java.sql.PreparedStatement;

public class QuickSort {

    public static void quickSort(int[] arr){
        recursion(arr,0,arr.length-1);
    }

    public static void recursion(int[] arr, int left, int right){

        if (left >= right){
            return;
        }
        int mid = benchmark(arr,left,right);
        recursion(arr,left,mid - 1);
        recursion(arr,mid + 1,right);
    }

    //单边快速排序
    private static int benchmark(int[] arr, int left, int right){

        int temp = arr[right];
        int i = left;
        int j = left;
        while (j < right){
            if (arr[j] < temp){
                if (i != j){
                    swap(arr,i,j);
                }
                i++;
            }
            j++;
        }
        swap(arr,i,right);
        return i;
    }

    //交换
    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


}

